package com.zzs.path;

import com.zzs.path.constant.PathConstants;
import com.zzs.path.entity.Node;
import com.zzs.path.entity.Edge;
import com.zzs.path.entity.Route;
import com.zzs.path.util.PathUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Demo01 {

    public static void main(String[] args) {

        // 准备数据
        List<Node> nodes = new ArrayList<>();
        List<Edge> edges = new ArrayList<>();
        getData(nodes, edges);

        // 将 nodeId 映射到 下标index 上
        Map<Integer, Integer> nodeToIndex = getNodeToIndex(nodes);

        // 获得地图
        int[][] graph = getGraph(nodes, edges, nodeToIndex);

        // 打印地图
        System.out.println("展示地图");
        printGraph(graph, nodes);

        Route route = PathUtils.TSP(graph, getTarget(), 0, nodeToIndex, nodes, edges);

        System.out.println("\n计算得到的路径："+route);
    }

    /**
     * 获取nodes集合中，nodeId 到 下标index 的映射
     * @param nodes
     * @return
     */
    public static Map<Integer,Integer> getNodeToIndex(List<Node> nodes){
        Map<Integer,Integer> nodeToIndex = new HashMap<>(nodes.size()+1);
        for(int i = 0;i<nodes.size();i++){
            nodeToIndex.put(nodes.get(i).getId(), i);
        }
        return nodeToIndex;
    }

    /**
     * 获取地图
     * @param nodes
     * @param edges
     * @param nodeToIndex
     * @return
     */
    public static int[][] getGraph(List<Node> nodes, List<Edge> edges, Map<Integer, Integer> nodeToIndex){
        int num = nodes.size();
        int[][] graph = new int[num][num];
        for(int i = 0; i < num; i++) {
            for(int j = 0; j < num; j++) {
                if(i == j){
                    graph[i][j] = 0;
                }else{
                    graph[i][j] = graph[j][i] = PathConstants.MAX_VALUE;
                }
            }
        }
        for(Edge edge : edges){
            int x = nodeToIndex.get(edge.getNode1Id());
            int y = nodeToIndex.get(edge.getNode2Id());
            graph[x][y] = graph[y][x] = edge.getDistance();
        }
        return graph;
    }

    /**
     * 获取 点集合 （含起点、目标点）
     * @return {10, 11, 12, 13}
     */
    public static int[] getTarget(){
        int[] target = {10, 11, 12, 13};
        return target;
    }

    public static void printGraph(int[][] graph, List<Node> nodes){
        int num = nodes.size();
        for(int i = 0; i<num; i++){
            System.out.print("\t"+nodes.get(i).getId());
        }
        System.out.println();
        for(int i = 0; i < num; i++) {
            System.out.print(nodes.get(i).getId()+"\t");
            for(int j = 0; j < num; j++) {
                System.out.print(graph[i][j]+"\t");
            }
            System.out.println();
        }
    }


    /**
     * 假设从数据库中获取了数据
     * @param nodes 待填充的点集合
     * @param edges 待填充的边集合
     */
    public static void getData(List<Node> nodes, List<Edge> edges){
        nodes.add(new Node(0, "左下", 0, 0, 0, 1, "A"));
        nodes.add(new Node(1, "左", 0, 0, 10, 1, "A"));
        nodes.add(new Node(2, "下", 0, 10, 0, 1, "A"));
        nodes.add(new Node(3, "左上", 0, 0, 20, 1, "A"));
        nodes.add(new Node(4, "中", 0, 10, 10, 1, "A"));
        nodes.add(new Node(5, "右下", 0, 20, 0, 1, "A"));
        nodes.add(new Node(6, "上", 0, 10, 20, 1, "A"));
        nodes.add(new Node(7, "右", 0, 20, 10, 1, "A"));
        nodes.add(new Node(10, "供", 1, 9, 0, 1, "A"));
        nodes.add(new Node(11, "科室1", 1, 0, 5, 1, "A"));
        nodes.add(new Node(12, "科室2", 1, 2, 10, 1, "A"));
        nodes.add(new Node(13, "科室3", 1, 9, 20, 1, "A"));
        nodes.add(new Node(14, "科室4", 1, 20, 5, 1, "A"));

        //edges.add(new Edge(0,0,1, 10, 0,1, "A"));
        edges.add(new Edge(0,0,11, 5, 0,1, "A"));
        edges.add(new Edge(0,1,11, 5, 0,1, "A"));
        //edges.add(new Edge(1,0,2, 10, 0,1, "A"));
        edges.add(new Edge(1,0,10, 9, 0,1, "A"));
        edges.add(new Edge(1,2,10, 1, 0,1, "A"));
        edges.add(new Edge(2,1,3, 10, 0,1, "A"));
        //edges.add(new Edge(3,1,4, 10, 0,1, "A"));
        edges.add(new Edge(3,1,12, 2, 0,1, "A"));
        edges.add(new Edge(3,4,12, 8, 0,1, "A"));
        edges.add(new Edge(4,2,4, 10, 0,1, "A"));
        edges.add(new Edge(5,2,5, 10, 0,1, "A"));
        //edges.add(new Edge(6,3,6, 10, 0,1, "A"));
        edges.add(new Edge(6,3,13, 9, 0,1, "A"));
        edges.add(new Edge(6,6,13, 1, 0,1, "A"));
        edges.add(new Edge(7,4,6, 10, 0,1, "A"));
        edges.add(new Edge(8,4,7, 10, 0,1, "A"));
        //edges.add(new Edge(9,5,7, 10, 0,1, "A"));
        edges.add(new Edge(9,5,14, 5, 0,1, "A"));
        edges.add(new Edge(9,7,14, 5, 0,1, "A"));
    }
}
